package top.lyc829.leetcode.T234;


import java.util.List;
import java.util.Stack;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    /**
     * 利用堆栈解决
     *
     * @param head 头节点
     * @return boolean
     */
    public boolean isPalindrome(ListNode head) {
        Stack<ListNode> s = new Stack<>();
        if (head == null || head.next == null) {
            return true;
        }
        ListNode tmp = head;
        while (tmp != null) {
            s.push(tmp);
            tmp = tmp.next;
        }
        while (!s.isEmpty()) {
            if (s.pop().val != head.val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    /**
     * 利用快慢指针，找到中间节点，反转后面的部分，前后比较是否相等
     *
     * @param head 头节点
     * @return boolean
     */
    public boolean isPalindrome2(ListNode head) {

        if (head == null || head.next == null) {
            return true;
        }

        ListNode leftLastNode = findLeftLastNode(head);
        ListNode reserveRightList = reserveRightList(leftLastNode.next);

        while (reserveRightList != null) {
            if (head.val != reserveRightList.val) {
                return false;
            }
            head = head.next;
            reserveRightList = reserveRightList.next;
        }
        return true;
    }

    /**
     * 反转链表
     *
     * @param head 头节点
     * @return
     */
    private ListNode reserveRightList(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode tmp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = tmp;
        }
        return pre;
    }

    /**
     * 找到前半部分链表的最后一个节点
     *
     * @param head
     * @return 前半部分链表的最后一个节点
     */
    private ListNode findLeftLastNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


    public static void main(String[] args) {
//        ListNode listNode1 = new ListNode(1,
//                new ListNode(2,
//                        new ListNode(2,
//                                new ListNode(4, null))));

        ListNode listNode1 = new ListNode(1, new ListNode(0, new ListNode(0, null)));

        Solution s = new Solution();
        boolean res = s.isPalindrome2(listNode1);
        System.out.println(res);

    }

}


